//一个关于用户信息的需求。由于公司业务越来越复杂，需要抽出一个用户系统，向各个业务系统提供用户的基本信息。由于业务方对用户信息的查询频率高，要特别注意性能问题。

//使用LRU算法解决这个问题。LRU全称，Least Recently Used，也就是最近最少使用的意思，是一种内存管理算法。该算法基于一种假设：长期不被使用的数据，在未来被用到的几率也不大。因此，当数据所占内存达到一定阈值时，我们要移除掉最近最少被使用的数据。在LRU算法中使用了一种数据结构，叫做**哈希链表**。这种结构使得原本没有顺序的key-value都具有了它的前驱和后驱的key-value，就像双向链表一样。按照这种特性，可以将key-value按照最后使用的时间进行排序，那么链表的最左端就是最近最少使用。

class Node {
    constructor(key, value) {
      this.key = key;
      this.value = value;
      this.next = null;
      this.prev = null;
    }
}
  
class LRUCache {
    constructor(limit) {
        this.head =null;
        this.end = null;
        // 缓存存储上限
        this.limit = limit;
        this.hashMap = new Map();
    }
    get(key) {
        let node = this.hashMap.get(key);
        if (node == null) {
         return null;
        }
        this.refreshNode(node);
        return node.value;
    }
    put(key, value) {
        let node = this.hashMap.get(key);
        if (node == null) {
            // 如果key不存在，就插入key-value
            if (this.hashMap.size >= this.limit) {
                let oldKey = this.removeNode(this.head);
                this.hashMap.delete(oldKey);
            }
            node = new Node(key, value);
            this.addNode(node);
            this.hashMap.set(key, node);
        } else {
            // 如果key存在，则更新key-value
            node.value = value
            this.refreshNode(node);
        }
    }
    remove(key) {
        let node = this.hashMap.get(key);
        this.removeNode(node);
        this.hashMap.delete(key);
    }
    // 刷新被访问的节点位置
    refreshNode(node) {
        // 如果访问的是尾节点，则无须移动节点
        if (node == this.end) {
          return;
        }
        // 移除节点
        this.removeNode(node);
        // 重新插入节点
        this.addNode(node);
    }
    // 删除节点
    removeNode(node) {
        if (node == this.head && node == this.end) {
        // 移除唯一节点
        this.head = null;
        this.end = null;
        } else if (node == this.end) {
        // 移除尾节点
        this.end = this.end.prev;
        this.end.next = null;
        } else if (node == this.head) {
        // 移除头节点
        this.head = this.head.next;
        this.head.prev = null;
        } else {
        // 移除中间节点
        node.prev.next = node.next;
        node.next.prev = node.prev;
        }
        return node.key;
    }
    // 尾部插入节点
    addNode(node) {
        if (this.end !== null) {
            this.end.next = node;
            node.prev = this.end;
            node.next = null;
        }
        this.end = node;
        if (this.head=== null) {
          this.head = node;
        }
    }
}

let lruCache = new LRUCache(5);
lruCache.put('001', '用户1信息');
lruCache.put('002', '用户2信息');
lruCache.put('003', '用户3信息');
lruCache.put('004', '用户4信息');
lruCache.put('005', '用户5信息');
// lruCache.get('002');
lruCache.put('004', '用户4信息更新');
lruCache.put('006', '用户6信息');

console.log(lruCache.hashMap);
console.log(lruCache.get('001')); // null
console.log(lruCache.get('006')); // 用户6信息